<!DOCTYPE HTML>
<html>
<head>
<meta charset="UTF-8">
<title>Section 11.8.4: Network rate optimization</title>
<link rel="canonical" href="http://cvxr.com/cvx/examples/cvxbook/Ch11_intpt_methods/html/log_utility_flow.html">
<link rel="stylesheet" href="../../../examples.css" type="text/css">
</head>
<body>
<div id="header">
<h1>Section 11.8.4: Network rate optimization</h1>
Jump to:&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#source">Source code</a>&nbsp;&nbsp;&nbsp;&nbsp;
<a href="#output">Text output</a>
&nbsp;&nbsp;&nbsp;&nbsp;
Plots
&nbsp;&nbsp;&nbsp;&nbsp;<a href="../../../index.html">Library index</a>
</div>
<div id="content">
<a id="source"></a>
<pre class="codeinput">
<span class="comment">% Boyd &amp; Vandenberghe "Convex Optimization"</span>
<span class="comment">% Argyrios Zymnis - 05/03/08</span>
<span class="comment">%</span>
<span class="comment">% We consider a network with n flows and L links. Each flow i,</span>
<span class="comment">% moves along a fixed predetermined path (i.e. a subset of the links)</span>
<span class="comment">% and has an associated rate x_i. Each link j has an associated capacity</span>
<span class="comment">% c_j. The total rate of all flows travelling along a link cannot exceed</span>
<span class="comment">% the link capacity. We can describe these link capacity limits using the</span>
<span class="comment">% flow-link incidence matrix A \in \reals^{L \times n}, where</span>
<span class="comment">% A_{ij} = 1, if flow j passes through link i and 0 otherwise.</span>
<span class="comment">% The link capacity constraints can be expressed as A*x &lt;= c</span>
<span class="comment">% In the network rate problem the variables are the flow rates x. The</span>
<span class="comment">% objective is to choose the flow rates to maximize a separate utility</span>
<span class="comment">% function U, given by</span>
<span class="comment">%           U(x) = U_1(x_1)+U_2(x_2)+...+U_n(x_n)</span>
<span class="comment">% The network rate optimization problem is then</span>
<span class="comment">%           maximize    U(x)</span>
<span class="comment">%           subject to  A*x &lt;= c</span>
<span class="comment">% Here we use U_i(x_i) = log x_i for all i</span>

<span class="comment">% Input data</span>
rand(<span class="string">'state'</span>,1)
L = 20;
n = 10;
k = 7; <span class="comment">%average links per flow</span>
A = double(rand(L,n) &lt;= k/L);
c = 0.9*rand(L,1)+0.1;

<span class="comment">% Solve network rate problem</span>
cvx_begin
    variable <span class="string">x(n)</span>;
    maximize(sum(log(x)))
    subject <span class="string">to</span>
        A*x &lt;= c
cvx_end
primal_obj = cvx_optval;

<span class="comment">% Solve dual problem to obtain link prices</span>
cvx_begin
    variable <span class="string">lambda(L)</span>;
    minimize(c'*lambda-sum(log(A'*lambda))-n)
    subject <span class="string">to</span>
        lambda &gt;= 0
cvx_end
dual_obj = cvx_optval;
</pre>
<a id="output"></a>
<pre class="codeoutput">
 
Successive approximation method to be employed.
   SDPT3 will be called several times to refine the solution.
   Original size: 50 variables, 30 equality constraints
   10 exponentials add 80 variables, 50 equality constraints
-----------------------------------------------------------------
 Cones  |             Errors              |
Mov/Act | Centering  Exp cone   Poly cone | Status
--------+---------------------------------+---------
 10/ 10 | 2.835e+00  8.576e-01  0.000e+00 | Solved
 10/ 10 | 9.542e-01  7.939e-02  0.000e+00 | Solved
 10/ 10 | 1.666e-01  2.253e-03  0.000e+00 | Solved
 10/ 10 | 2.204e-02  3.875e-05  0.000e+00 | Solved
  9/ 10 | 2.601e-03  5.374e-07  0.000e+00 | Solved
  0/  7 | 3.015e-04  6.607e-09  0.000e+00 | Solved
-----------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): -31.5685
 
 
Successive approximation method to be employed.
   SDPT3 will be called several times to refine the solution.
   Original size: 50 variables, 20 equality constraints
   10 exponentials add 80 variables, 50 equality constraints
-----------------------------------------------------------------
 Cones  |             Errors              |
Mov/Act | Centering  Exp cone   Poly cone | Status
--------+---------------------------------+---------
 10/ 10 | 5.283e+00  1.547e+00  1.450e-09 | Solved
 10/ 10 | 1.412e+00  1.312e-01  2.806e-09 | Solved
 10/ 10 | 1.306e-01  1.080e-03  2.898e-09 | Solved
 10/ 10 | 1.689e-02  1.815e-05  2.609e-09 | Solved
 10/ 10 | 2.271e-03  3.237e-07  2.635e-09 | Solved
  0/  7 | 3.067e-04  4.624e-09  2.633e-09 | Solved
-----------------------------------------------------------------
Status: Solved
Optimal value (cvx_optval): -31.5685
 
</pre>
</div>
</body>
</html>